home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / src / cmds / cc / g++-dist / case.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-01-30  |  17.7 KB  |  612 lines
  1. #ifndef FIRST_PSEUDO_REGISTER
  2. #define NULL 0
  3. #include "config.h"
  4. #include "rtl.h"
  5. #include "tree.h"
  6. #include "insn-flags.h"
  7. #endif
  8.  
  9. /* Functions and data structures for expanding case statements.  */
  10.  
  11. /* Case label structure, used to hold info on labels within case
  12.    statements.  We handle "range" labels; for a single-value label
  13.    as in C, the high and low limits are the same.  */
  14.  
  15. struct case_node
  16. {
  17.   struct case_node    *left;
  18.   struct case_node    *right;
  19.   struct case_node    *parent;
  20.   tree            low;
  21.   tree            high;
  22.   tree            test_label;
  23.   tree            code_label;
  24. };
  25.  
  26. typedef struct case_node case_node;
  27. typedef struct case_node *case_node_ptr;
  28.  
  29. void balance_case_nodes ();
  30. void emit_case_nodes ();
  31. void group_case_nodes ();
  32. void emit_jump_if_reachable ();
  33.  
  34. /* Generate code to jump to LABEL if OP1 and OP2 are equal.  */
  35.  
  36. static void
  37. do_jump_if_equal (op1, op2, label, unsignedp)
  38.      rtx op1, op2, label;
  39.      int unsignedp;
  40. {
  41.   if (GET_CODE (op1) == CONST_INT
  42.       && GET_CODE (op2) == CONST_INT)
  43.     {
  44.       if (INTVAL (op1) == INTVAL (op2))
  45.     emit_jump (label);
  46.     }
  47.   else
  48.     {
  49.       emit_cmp_insn (op1, op2, 0, unsignedp, 0);
  50.       emit_jump_insn (gen_beq (label));
  51.     }
  52. }
  53.  
  54. /* Not all case values are encountered equally.  This function
  55.    uses a heuristic to weight case labels, in cases where that
  56.    looks like a reasonable thing to do.
  57.  
  58.    Right now, all we try to guess is text, and we establish the
  59.    following weights:
  60.  
  61.     chars above space:    16
  62.     digits:            16
  63.     default:        12
  64.     space, punct:        8
  65.     tab:            4
  66.     newline:        2
  67.     other "\" chars:    1
  68.     remaining chars:    0
  69.  
  70.    Under this weighting, ranges are automagically taken care of.  */
  71.  
  72. #include <ctype.h>
  73. static char *cost_table;
  74. static int use_cost_table;
  75.  
  76. void
  77. estimate_case_costs (node, default_label)
  78.      case_node_ptr node;
  79.      rtx default_label;
  80. {
  81.   tree min_ascii = build_int_2 (-1, -1);
  82.   tree max_ascii = convert (TREE_TYPE (node->high), build_int_2 (127, 0));
  83.   case_node_ptr n;
  84.   use_cost_table = 0;
  85.  
  86.   /* If the user is running without default, who are we
  87.      to guess where values are likely to land?  */
  88.   if (default_label == 0)
  89.     return;
  90.  
  91.   /* See if all the case expressions look like text.  It is text if the lowest
  92.      constant is >= -1 and the highest constant is <= 127.  If the case
  93.      expression is unsigned, suppress the test for >= -1, since it would always
  94.      be true.  */
  95.   for (n = node; n; n = n->right)
  96.     if ((! TREE_UNSIGNED (TREE_TYPE (n->low))
  97.      && tree_int_cst_lt (n->low, min_ascii))
  98.     || tree_int_cst_lt (max_ascii, n->high))
  99.     return;
  100.  
  101.   /* All interesting values with within the range of
  102.      interesting ASCII characters.  */
  103.   if (cost_table == NULL)
  104.     {
  105.       int i;
  106.       cost_table = ((char *)malloc (129)) + 1;
  107.       bzero (cost_table-1, 128);
  108.       for (i = 0; i < 128; i++)
  109.     {
  110.       if (isalnum (i))
  111.         cost_table[i] = 16;
  112.       else if (ispunct (i))
  113.         cost_table[i] = 8;
  114.       else if (iscntrl (i))
  115.         cost_table[i] = -1;
  116.     }
  117.       cost_table[' '] = 8;
  118.       cost_table['\t'] = 4;
  119.       cost_table['\0'] = 4;
  120.       cost_table['\n'] = 2;
  121.       cost_table['\f'] = 1;
  122.       cost_table['\v'] = 1;
  123.       cost_table['\b'] = 1;
  124.     }
  125.   use_cost_table = 1;
  126. }
  127.  
  128. /* Scan an ordered list of case nodes
  129.    combining those with consecutive values or ranges.
  130.  
  131.    Eg. three separate entries 1: 2: 3: become one entry 1..3:  */
  132.  
  133. void
  134. group_case_nodes (head)
  135.      case_node_ptr head;
  136. {
  137.   case_node_ptr node = head;
  138.  
  139.   while (node)
  140.     {
  141.       rtx lb = next_real_insn (label_rtx (node->code_label));
  142.       case_node_ptr np = node;
  143.  
  144.       /* Try to group the successors of NODE with NODE.  */
  145.       while (((np = np->right) != 0)
  146.          /* Do they jump to the same place?  */
  147.          && next_real_insn (label_rtx (np->code_label)) == lb
  148.          /* Are their ranges consecutive?  */
  149.          && tree_int_cst_equal (np->low,
  150.                     combine (PLUS_EXPR, node->high,
  151.                          integer_one_node)))
  152.     {
  153.       node->high = np->high;
  154.     }
  155.       /* NP is the first node after NODE which can't be grouped with it.
  156.      Delete the nodes in between, and move on to that node.  */
  157.       node->right = np;
  158.       node = np;
  159.     }
  160. }
  161.  
  162. /* Take an ordered list of case nodes
  163.    and transform them into a near optimal binary tree,
  164.    on the assumtion that any target code selection value is as
  165.    likely as any other.
  166.  
  167.    The transformation is performed by splitting the ordered
  168.    list into two equal sections plus a pivot.  The parts are
  169.    then attached to the pivot as left and right branches.  Each
  170.    branch is is then transformed recursively.  */
  171.  
  172. void
  173. balance_case_nodes (head, parent)
  174.      case_node_ptr *head;
  175.      case_node_ptr parent;
  176. {
  177.   register case_node_ptr np;
  178.  
  179.   np = *head;
  180.   if (np)
  181.     {
  182.       int cost = 0;
  183.       int i = 0;
  184.       int ranges = 0;
  185.       register case_node_ptr *npp;
  186.       case_node_ptr left;
  187.  
  188.       /* Count the number of entries on branch.
  189.      Also count the ranges.  */
  190.       while (np)
  191.     {
  192.       if (!tree_int_cst_equal (np->low, np->high))
  193.         {
  194.           ranges++;
  195.           if (use_cost_table)
  196.         {
  197.           int hi_cost = cost_table[TREE_INT_CST_LOW (np->high)];
  198.           if (hi_cost < 0)
  199.             use_cost_table = 0;
  200.           else
  201.             cost += hi_cost;
  202.         }
  203.         }
  204.       if (use_cost_table)
  205.         {
  206.           int lo_cost = cost_table[TREE_INT_CST_LOW (np->low)];
  207.           if (lo_cost < 0)
  208.         use_cost_table = 0;
  209.           else
  210.         cost += lo_cost;
  211.         }
  212.       else
  213.         cost += 1;
  214.       i++;
  215.       np = np->right;
  216.     }
  217.       if (i > 2)
  218.     {
  219.       /* Split this list if it is long enough for that to help.  */
  220.       npp = head;
  221.       left = *npp;
  222.       if (use_cost_table)
  223.         {
  224.           /* Find the place in the list that bisects the list's total cost,
  225.          Here I gets half the total cost.  */
  226.           int n_moved = 0;
  227.           i = (cost + 1) / 2;
  228.           while (1)
  229.         {
  230.           /* Skip nodes while their cost does not reach that amount.  */
  231.           if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
  232.             i -= cost_table[TREE_INT_CST_LOW ((*npp)->high)];
  233.           i -= cost_table[TREE_INT_CST_LOW ((*npp)->low)];
  234.           if (i <= 0)
  235.             break;
  236.           npp = &(*npp)->right;
  237.           n_moved += 1;
  238.         }
  239.           if (n_moved == 0)
  240.         {
  241.           /* Leave this branch lopsided, but optimize left-hand
  242.              side and fill in `parent' fields for right-hand side.  */
  243.           np = *head;
  244.           np->parent = parent;
  245.           balance_case_nodes (&np->left, np);
  246.           for (; np->right; np = np->right)
  247.             np->right->parent = np;
  248.           return;
  249.         }
  250.         }
  251.       /* If there are just three nodes, split at the middle one.  */
  252.       else if (i == 3)
  253.         npp = &(*npp)->right;
  254.       else
  255.         {
  256.           /* Find the place in the list that bisects the list's total cost,
  257.          where ranges count as 2.
  258.          Here I gets half the total cost.  */
  259.           i = (i + ranges + 1) / 2;
  260.           while (1)
  261.         {
  262.           /* Skip nodes while their cost does not reach that amount.  */
  263.           if (!tree_int_cst_equal ((*npp)->low, (*npp)->high))
  264.             i--;
  265.           i--;
  266.           if (i <= 0)
  267.             break;
  268.           npp = &(*npp)->right;
  269.         }
  270.         }
  271.       *head = np = *npp;
  272.       *npp = 0;
  273.       np->parent = parent;
  274.       np->left = left;
  275.  
  276.       /* Optimize each of the two split parts.  */
  277.       balance_case_nodes (&np->left, np);
  278.       balance_case_nodes (&np->right, np);
  279.     }
  280.       else
  281.     {
  282.       /* Else leave this branch as one level,
  283.          but fill in `parent' fields.  */
  284.       np = *head;
  285.       np->parent = parent;
  286.       for (; np->right; np = np->right)
  287.         np->right->parent = np;
  288.     }
  289.     }
  290. }
  291.  
  292. /* Search the parent sections of the case node tree
  293.    to see if a test for the lower bound of NODE would be redundant.
  294.  
  295.    The instructions to synthesis the case decision tree are
  296.    output in the same order as nodes are processed so it is
  297.    known that if a parent node checks the range of the current
  298.    node minus one that the current node is bounded at its lower
  299.    span.  Thus the test would be redundant.  */
  300.  
  301. static int
  302. node_has_low_bound (node)
  303.      case_node_ptr node;
  304. {
  305.   tree low_minus_one;
  306.   case_node_ptr pnode;
  307.  
  308.   if (node->left)
  309.     {
  310.       low_minus_one = combine (MINUS_EXPR, node->low, integer_one_node);
  311.       /* Avoid the screw case of overflow where low_minus_one is > low.  */
  312.       if (tree_int_cst_lt (low_minus_one, node->low))
  313.     for (pnode = node->parent; pnode; pnode = pnode->parent)
  314.       {
  315.         if (tree_int_cst_equal (low_minus_one, pnode->high))
  316.           return 1;
  317.         /* If a parent node has a left branch we know that none
  318.            of its parents can have a high bound of our target
  319.            minus one so we abort the search.  */
  320.         if (node->left)
  321.           break;
  322.       }
  323.     }
  324.   return 0;
  325. }
  326.  
  327. /* Search the parent sections of the case node tree
  328.    to see if a test for the upper bound of NODE would be redundant.
  329.  
  330.    The instructions to synthesis the case decision tree are
  331.    output in the same order as nodes are processed so it is
  332.    known that if a parent node checks the range of the current
  333.    node plus one that the current node is bounded at its upper
  334.    span.  Thus the test would be redundant.  */
  335.  
  336. static int
  337. node_has_high_bound (node)
  338.      case_node_ptr node;
  339. {
  340.   tree high_plus_one;
  341.   case_node_ptr pnode;
  342.  
  343.   if (node->right == 0)
  344.     {
  345.       high_plus_one = combine (PLUS_EXPR, node->high, integer_one_node);
  346.       /* Avoid the screw case of overflow where high_plus_one is > high.  */
  347.       if (tree_int_cst_lt (node->high, high_plus_one))
  348.     for (pnode = node->parent; pnode; pnode = pnode->parent)
  349.       {
  350.         if (tree_int_cst_equal (high_plus_one, pnode->low))
  351.           return 1;
  352.         /* If a parent node has a right branch we know that none
  353.            of its parents can have a low bound of our target
  354.            plus one so we abort the search.  */
  355.         if (node->right)
  356.           break;
  357.       }
  358.     }
  359.   return 0;
  360. }
  361.  
  362. /* Search the parent sections of the
  363.    case node tree to see if both tests for the upper and lower
  364.    bounds of NODE would be redundant.  */
  365.  
  366. static int
  367. node_is_bounded (node)
  368.      case_node_ptr node;
  369. {
  370.   if (node->left || node->right)
  371.     return 0;
  372.   return node_has_low_bound (node) && node_has_high_bound (node);
  373. }
  374.  
  375. /*  Emit an unconditional jump to LABEL unless it would be dead code.  */
  376.  
  377. void
  378. emit_jump_if_reachable (label)
  379.      rtx label;
  380. {
  381.   rtx last_insn;
  382.  
  383.   if (GET_CODE (get_last_insn ()) != BARRIER)
  384.     emit_jump (label);
  385. }
  386.  
  387. /* Emit step-by-step code to select a case for the value of INDEX.
  388.    The thus generated decision tree follows the form of the
  389.    case-node binary tree NODE, whose nodes represent test conditions.
  390.    UNSIGNEDP is nonzero if we should do unsigned comparisons.
  391.  
  392.    Care is taken to prune redundant tests from the decision tree
  393.    by detecting any boundary conditions already checked by
  394.    emitted rtx.  (See node_has_high_bound, node_has_low_bound
  395.    and node_is_bounded, above.)
  396.  
  397.    Where the test conditions can be shown to be redundant we emit
  398.    an unconditional jump to the target code.  As a further
  399.    optimization, the subordinates of a tree node are examined to
  400.    check for bounded nodes.  In this case conditional and/or
  401.    unconditional jumps as a result of the boundary check for the
  402.    current node are arranged to target the subordinates associated
  403.    code for out of bound conditions on the current node node.  */
  404.  
  405. void
  406. emit_case_nodes (index, node, default_label, unsignedp)
  407.      rtx index;
  408.      case_node_ptr node;
  409.      rtx default_label;
  410.      int unsignedp;
  411. {
  412.   /* If INDEX has an unsigned type, we must make unsigned branches.  */
  413.   typedef rtx rtx_function ();
  414.   rtx_function *gen_bgt_pat = unsignedp ? gen_bgtu : gen_bgt;
  415.   rtx_function *gen_bge_pat = unsignedp ? gen_bgeu : gen_bge;
  416.   rtx_function *gen_blt_pat = unsignedp ? gen_bltu : gen_blt;
  417.   rtx_function *gen_ble_pat = unsignedp ? gen_bleu : gen_ble;
  418.   int defaulted_left = 0;
  419.   int defaulted_right = 0;
  420.  
  421.   if (node->test_label)
  422.     {
  423.       /* If this test node requires a label it follows that
  424.      it must be preceeded by an unconditional branch.
  425.      If control can pass to this point we can assume that
  426.      a "br default" is in order.  */
  427.       emit_jump_if_reachable (default_label);
  428.       expand_label (node->test_label);
  429.     }
  430.   if (tree_int_cst_equal (node->low, node->high))
  431.     {
  432.       /* Node is single valued.  */
  433.       do_jump_if_equal (index, expand_expr (node->low, 0, VOIDmode, 0),
  434.             label_rtx (node->code_label), unsignedp);
  435.       if (node->right)
  436.     {
  437.       if (node->left)
  438.         {
  439.           /* This node has children on either side.  */
  440.           emit_cmp_insn (index, expand_expr (node->high, 0, VOIDmode, 0), 0, unsignedp, 0);
  441.  
  442.           if (node_is_bounded (node->right))
  443.         {
  444.           emit_jump_insn ((*gen_bgt_pat) (label_rtx (node->right->code_label)));
  445.           if (node_is_bounded (node->left))
  446.             emit_jump (label_rtx (node->left->code_label));
  447.           else
  448.             emit_case_nodes (index, node->left,
  449.                      default_label, unsignedp);
  450.         }
  451.           else
  452.         {
  453.           if (node_is_bounded (node->left))
  454.             emit_jump_insn ((*gen_blt_pat) (label_rtx (node->left->code_label)));
  455.           else
  456.             {
  457.               node->right->test_label =
  458.             build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
  459.               emit_jump_insn ((*gen_bgt_pat) (label_rtx (node->right->test_label)));
  460.               emit_case_nodes (index, node->left,
  461.                        default_label, unsignedp);
  462.             }
  463.           emit_case_nodes (index, node->right,
  464.                    default_label, unsignedp);
  465.         }
  466.         }
  467.       else
  468.         {
  469.           /* Here we have a right child but no left
  470.          so we issue conditional branch to default
  471.          and process the right child.  */
  472.  
  473.           /* Omit the conditional branch to default
  474.          if we it avoid only one right child;
  475.          it costs too much space to save so little time.  */
  476.           if (node->right->right && !node_has_low_bound (node))
  477.         {
  478.           emit_cmp_insn (index, expand_expr (node->high, 0, VOIDmode, 0), 0, unsignedp, 0);
  479.           emit_jump_insn ((*gen_blt_pat) (default_label));
  480.         }
  481.           if (node_is_bounded (node->right))
  482.         emit_jump (label_rtx (node->right->code_label));
  483.           else
  484.         emit_case_nodes (index, node->right, default_label, unsignedp);
  485.         }
  486.     }
  487.       else if (node->left)
  488.     {
  489.       if (use_cost_table
  490.           && ! defaulted_right
  491.           && cost_table[TREE_INT_CST_LOW (node->high)] < 12)
  492.         {
  493.           /* If our "most probably entry" is less probable
  494.          than the default label, emit a jump to
  495.          the default label using condition codes
  496.          already lying around.  With no right branch,
  497.          a branch-greater-than will get us to the default
  498.          label correctly.  */
  499.           emit_cmp_insn (index, expand_expr (node->high, 0, VOIDmode, 0), 0, unsignedp, 0);
  500.           emit_jump_insn ((*gen_bgt_pat) (default_label));
  501.           /* No sense doing this too often.  */
  502.           defaulted_right = 1;
  503.         }
  504.       if (node_is_bounded (node->left))
  505.         emit_jump (label_rtx (node->left->code_label));
  506.       else
  507.         emit_case_nodes (index, node->left, default_label, unsignedp);
  508.     }
  509.     }
  510.   else
  511.     {
  512.       /* Node is a range.  */
  513.       if (node->right)
  514.     {
  515.       if (node->left)
  516.         {
  517.           emit_cmp_insn (index, expand_expr (node->high, 0, VOIDmode, 0), 0, unsignedp, 0);
  518.           if (node_is_bounded (node->right))
  519.         {
  520.           /* Right hand node is fully bounded so we can
  521.              eliminate any testing and branch directly
  522.              to the target code.  */
  523.           emit_jump_insn ((*gen_bgt_pat) (label_rtx (node->right->code_label)));
  524.         }
  525.           else
  526.         {
  527.           /* Right hand node requires testing so create
  528.              a label to put on the cmp code.  */
  529.           node->right->test_label =
  530.             build_decl (LABEL_DECL, NULL_TREE, NULL_TREE);
  531.           emit_jump_insn ((*gen_bgt_pat) (label_rtx (node->right->test_label)));
  532.         }
  533.           emit_cmp_insn (index, expand_expr (node->low, 0, VOIDmode, 0), 0, unsignedp, 0);
  534.           emit_jump_insn ((*gen_bge_pat) (label_rtx (node->code_label)));
  535.           if (node_is_bounded (node->left))
  536.         {
  537.           /* Left hand node is fully bounded so we can
  538.              eliminate any testing and branch directly
  539.              to the target code.  */
  540.           emit_jump (label_rtx (node->left->code_label));
  541.         }
  542.           else
  543.         emit_case_nodes (index, node->left, default_label, unsignedp);
  544.           /* If right node has been given a test label above
  545.          we must process it now.  */
  546.           if (node->right->test_label)
  547.         emit_case_nodes (index, node->right, default_label, unsignedp);
  548.         }
  549.       else
  550.         {
  551.           if (!node_has_low_bound (node))
  552.         {
  553.           emit_cmp_insn (index, expand_expr (node->low, 0, VOIDmode, 0), 0, unsignedp, 0);
  554.           emit_jump_insn ((*gen_blt_pat) (default_label));
  555.         }
  556.           emit_cmp_insn (index, expand_expr (node->high, 0, VOIDmode, 0), 0, unsignedp, 0);
  557.           emit_jump_insn ((*gen_ble_pat) (label_rtx (node->code_label)));
  558.           if (node_is_bounded (node->right))
  559.         {
  560.           /* Right hand node is fully bounded so we can
  561.              eliminate any testing and branch directly
  562.              to the target code.  */
  563.           emit_jump (label_rtx (node->right->code_label));
  564.         }
  565.           else
  566.         emit_case_nodes (index, node->right, default_label, unsignedp);
  567.         }
  568.     }
  569.       else if (node->left)
  570.     {
  571.       if (!node_has_high_bound (node))
  572.         {
  573.           emit_cmp_insn (index, expand_expr (node->high, 0, VOIDmode, 0), 0, unsignedp, 0);
  574.           emit_jump_insn ((*gen_bgt_pat) (default_label));
  575.         }
  576.       emit_cmp_insn (index, expand_expr (node->low, 0, VOIDmode, 0), 0, unsignedp, 0);
  577.       emit_jump_insn ((*gen_bge_pat) (label_rtx (node->code_label)));
  578.       if (node_is_bounded (node->left))
  579.         {
  580.           /* Left hand node is fully bounded so we can
  581.          eliminate any testing and branch directly
  582.          to the target code.  */
  583.           emit_jump (label_rtx (node->left->code_label));
  584.         }
  585.       else
  586.         emit_case_nodes (index, node->left, default_label, unsignedp);
  587.     }
  588.       else
  589.     {
  590.       /* Node has no children so we check low and
  591.          high bounds to remove redundant tests. In practice
  592.          only one of the limits may be bounded or the parent
  593.          node will have emmited a jump to our target code.  */
  594.       if (!node_has_high_bound (node))
  595.         {
  596.           emit_cmp_insn (index, expand_expr (node->high, 0, VOIDmode, 0), 0, unsignedp, 0);
  597.           emit_jump_insn ((*gen_bgt_pat) (default_label));
  598.         }
  599.       if (!node_has_low_bound (node))
  600.         {
  601.           emit_cmp_insn (index, expand_expr (node->low, 0, VOIDmode, 0), 0, unsignedp, 0);
  602.           emit_jump_insn ((*gen_bge_pat) (label_rtx (node->code_label)));
  603.         }
  604.       /* We allow the default case to drop through since
  605.          it will picked up by calls to `jump_if_reachable'
  606.          either on the next test label or at the end of
  607.          the decision tree emission.  */
  608.     }
  609.     }
  610. }
  611.  
  612.